/**
 * 插入排序
 * @author dc
 * @Classname Insertion
 * @Date 2020/1/3 19:36
 */
public class Insertion extends BaseSort{

    /**
     * 将数组按升序排序
     * @param a
     */
    public static void sort(Comparable[] a) {
        int N=a.length;
        for(int i=1;i<N;i++){
            //将a[i]插入到a[i-1],a[i-2],a[i-3]....之中
            //当后一个数比前一个数大,并且j不等于0时,交换两个数位置,让大的数在后面
            for(int j=i;j>0&&less(a[j],a[j-1]);j--){
                exch(a,j,j-1);
            }
        }
    }

}
